package leetcode.common.utils;

// 二叉树工具类

import leetcode.common.entitys.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class BtreeUtils<T> {

    // 用数组建立二叉排序树
    public static TreeNode bulidBSTByArray(int[] A) {
        TreeNode root = new TreeNode(A[0]);
        for (int i = 1; i < A.length; i++) {
            createBST(root, A[i]);
        }
        return root;
    }

    private static void createBST(TreeNode node, int val) {
        if (val < node.val) {
            if (node.left == null) {
                node.left = new TreeNode(val);
            } else
                createBST(node.left, val);
        } else {
            if (node.right == null) {
                node.right = new TreeNode(val);
            } else
                createBST(node.right, val);
        }
    }

    // 用数组建立普通二叉树
    public static TreeNode buildBinaryTreeByArray(Integer[] A, int index) {
        TreeNode root = null;
        TreeNode pos = null;
        boolean startup = true;
        for (int j = index + 1; j < A.length; j += 2) {

            if (true == startup) {
                pos = new TreeNode(A[index]);
                root = pos;
                startup = false;
            }

            pos.left = null == A[j] ? null : new TreeNode(A[j]);
            if (j + 1 < A.length)
                pos.right = null == A[j + 1] ? null : new TreeNode(A[j + 1]);

            if (null != pos.left) {
                pos = pos.left;
            } else if (null != pos.right) {
                pos = pos.right;
            }
        }

        return root;
    }

    // 层序遍历打印二叉树
    public static void levelOrderPrintBST(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null)
            return;
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null)
                continue;
            else
                System.out.println(node.val);
            queue.offer(node.left);
            queue.offer(node.right);
        }
    }
}
